A. Field of the Invention
The present invention relates to a method and device for selecting data symbols to be transmitted in a digital communication system. Although the invention provides a method of signal point mapping and may be applied to any data communication system, it is particularly well suited for use in systems where the selection of constellation points is subject to relatively strict criteria, e.g., where signal points within a constellation are not equally spaced, or where a constellation or constituent sub-constellations may contain a number of points that is not a power of two. The method described herein is also well suited for the case where the number of elements within the constellations varies from symbol to symbol.
Such restrictions are encountered in communication systems that use the public digital telephone network where one side of the communication link (typically a server) has direct digital access to the network. In such a system the constellation selection is limited in part by the presence of Robbed-Bit-Signaling (RBS) and/or a Network Digital Attenuators (NDA), and power constraints imposed by government (e.g., FCC) regulations. These techniques also can be used to help minimize the impact of RBS/NDA on the data rate over such channels.
B. Description of the Related Art
As stated above, the signaling method and device described herein may be used in many types of digital communication systems. Generally, modulation techniques for the transmission of digital information involve modulating the amplitude and phase of a carrier frequency. A baseband signal (an unmodulated information sequence such as a train of pulses of various amplitudes) may be used to modify the amplitude of a carrier frequency sine wave. Because a carrier may also be separated into orthogonal cosine and sine components (also referred to as inphase (I) and quadrature (Q) channels), a modulated carrier may be thought of as the sum of a modulated sine wave and a modulated cosine wave.
As is well known in the art, a two-dimensional plane, or I-Q plane, is used as a shorthand notation to represent the amplitude and phase of the carrier. The signals that make up a signal constellation are represented as points in the I-Q plane, which are usually set out in a grid-like fashion. A particular signal point may be specified as a coordinate pair in the I-Q plane. The points in the I-Q plane are also generally referred to as a baseband representation of the signal because the points represent the amplitudes by which the sine and cosine components of a carrier will be modified. Each "signal point" is also referred to herein as a "symbol."
While the invention described herein is applicable to systems that use modulated carriers as described above, the preferred embodiments are essentially baseband systems that do not involve the modulation of a carrier. Consequently, the signal points are selected from a single-dimensional signal space, as opposed to a two-dimensional inphase/quadrature signal space. The system for which the invention is particularly well suited uses the public digital telephone network.
1. Digital Telephone Network
For many years the public digital telephone network (DTN) has been used for data transmission between modems. Typically, a modulated carrier is sent over a local loop to a service provider (e.g., a Regional Bell Operating Company), whereupon the service provider quantizes the signal for transmission through the DTN. A service provider that is located near the receiving location converts the digital signal back to an analog signal for transmission over a local loop to the receiving modem. This system is limited in the maximum achievable data rate at least in part by the sampling rate of the quantizers, which is typically 8 kHz (which rate is also the corresponding channel transmission rate, or clock rate, of the DTN).
Furthermore, the analog-to-digital (A/D) and digital-to-analog (D/A) conversions are typically performed in accordance with a non-linear quantizing rule. In North America, this conversion rule is known as L-law. A similar non-linear sampling technique known as A-law is used in certain areas of the world such as Europe. The non-linear A/D and D/A conversion is generally performed by a codec (coder/decoder) device located at the interfaces between the DTN and local loops.
It has been recognized that a data distribution system using the public telephone network can overcome certain aspects of the aforesaid limitations by providing a digital data source connected directly to the DTN, without an intervening codec. In such a system, the telephone network routes digital signals from the data source to a client's local subscriber loop without any intermediary analog facilities, such that the only analog portion of the link from the data source to the client is the client's local loop (plus the associated analog electronics at both ends of the loop). The only codes in the transmission path is the one at the DTN end of the client's subscriber loop.
FIG. 1 shows a block diagram of a data distribution system. The system includes a data source 10, or server, having a direct digital connection 12 to a digital telephone network (DTN) 14. A client 16 is connected to the DTN 12 by a subscriber loop 18 that is typically a two-wire, or twisted-pair, cable. The DTN routes digital signals from the data source 10 to the client's local subscriber loop 18 without any intermediary analog facilities such that the only analog portion of the link from the server 10 to the client 16 is the subscriber loop 18. The analog portion thus includes the channel characteristics of the subscriber loop 18 plus the associated analog electronics at both ends of the subscriber loop 18. The analog electronics are well known to those skilled in the art and typically include a subscriber line interface card at the central office that includes a codec, as well as circuitry used to generate and interpret call progress signals (ring voltage, on-hook and off-hook detection, etc.). In the system of FIG. 1, the only D/A converter in the transmission path from the server 10 to the client 16 is located at the DTN 14 end of the subscriber loop 18. It is understood that the client-side, or subscriber-side, equipment may incorporate an A/D and D/A for its internal signal processing, as is typical of present day modem devices. For the reverse channel, the only A/D converter in the path from the client 16 to the server 10 is also at the DTN 14 end of the subscriber loop 18.
In the system of FIG. 1, the server 10, having direct digital access to the DTN 14 may be a single computer, or may include a communications hub that provides digital access to a number of computers or processing units. Such a hub/server is disclosed in U.S. Pat. No. 5,528,595, issued Jun. 18, 1996, the contents of which are incorporated herein by reference. Another hub/server configuration is disclosed in U.S. Pat. No. 5,577,105, issued Nov. 19, 1996, the contents of which are also incorporated herein by reference.
In the system shown in FIG. 1, digital data can be input to the DTN 14 as 8-bit bytes (octets) at the 8 kHz clock rate of the DTN. This is commonly referred to as a DS-0 signal format. At the interface between the DTN 14 and the subscriber loop 18, the DTN 14 codec converts each byte to one of 255 analog voltage levels (two different octets each represent 0 volts) that are sent over the subscriber loop 18 and received by a decoder at the client's location. The last leg of this system, i.e., the local loop 18 from the network codec to the client 16, may be viewed as a type of baseband data transmission system because no carrier is being modulated in the transmission of the data. The baseband signal set contains the positive and negative voltage pulses output by the codec in response to the binary octets sent over the DTN. The client 16, as shown in FIG. 1, may be referred to herein as a PCM modem.
FIG. 3 shows a .mu.-law to linear conversion graph for one-half of the .mu.-law codeword set used by the DTN 14 codec. As shown in FIG. 3, the analog voltages (shown as decimal equivalents of linear codewords having 16 bits) corresponding to the quantization levels are non-uniformly spaced and follow a generally logarithmic curve. In other words, the increment in the analog voltage level produced from one codeword to the next is not linear, but depends on the mapping as shown in FIG. 3. Note that the vertical scale of FIG. 3 is calibrated in integers from 0 to 32,124. These numbers correspond to a linear 16-bit A/D converter. As is known to those of ordinary skill in the art, the sixteenth bit is a sign bit which provides integers from 0 to -32,124 which correspond to octets from 0 to 127, not shown in FIG. 3. Thus FIG. 3 can be viewed as a conversion between the logarithmic binary data and the corresponding linear 16-bit binary data. It can also be seen in FIG. 3 that the logarithmic function of the standard conversion format is approximated by a series of 8 linear segments.
The conversion from octet to analog voltage is well known, and as stated above, is based on a system called .mu.-law coding in North America and A-law coding in Europe. Theoretically, there are 256 points represented by the 256 possible octets, or .mu.-law codewords. The format of the .mu.-law codewords is shown in FIG. 2, where the most significant bit b.sub.7 indicates the sign, the three bits b.sub.6 -b.sub.4 represent the linear segment, and the four bits, b.sub.0 -b.sub.3 indicate the step along the particular linear segment. These points are symmetric about zero; i.e., there are 128 positive and 128 negative levels, including two encodings of zero. Since there are 254 non-zero points, the maximum number of bits that can be sent per signaling interval (symbol) is just under 8 bits. A .mu.-law or A-law codeword may be referred to herein as a PCM codeword. It is actually the PCM codeword that results in the DTN 20 codec to output a particular analog voltage. The codeword and the corresponding voltage may be referred to herein as "points."
Other factors, such as robbed-bit signaling, digital attenuation (pads), channel distortion and noise introduced by the subscriber loop, and the crowding of points at the smaller voltage amplitudes and the associated difficulty in distinguishing between them at the decoder/receiver, may reduce the maximum attainable bit rate. Robbed Bit Signaling (RBS) involves the periodic use of the least significant bit (LSB) of the PCM codeword by the DTN 14 to convey control information. Usually the robbed bit is replaced with a logical `1` before transmission to the client 16. In addition, due to the fact that a channel might traverse several digital networks before arriving at the terminus of the DTN 14, more than one PCM codeword per 6 time slots could have a bit robbed by each network, with each network link robbing a different lsb.
To control power levels, some networks impose digital attenuators that act on the PCM codewords to convert them to smaller values. Unlike most analog attenuators, a network digital attenuator (NDA) is not linear. Because there are a finite number of digital levels to choose from, the NDA will be unable to divide each codeword in half. This causes distortion of the analog level ultimately transmitted by the codec over the subscriber loop 18. RBS and an NDA can coexist in many combinations. For example, a PCM interval could have a robbed bit of type `1`, followed by an NDA followed by another robbed bit of type `1`. This could happen to a byte if a channel goes through a bit-robbed link, then through an NDA, then another bit-robbed link before reaching the DTN 14 codec.
It is evident that the above-described data transmission system imposes many constraints on the points that may be used to form a signal constellation. Inter alia, the octets will always be converted to non-linearly spaced voltage pulses in accordance with .mu.-law or A-law conversion; lsbs may be robbed during some time slots making some points unavailable in that time slot; digital attenuators may make some points ambiguous; and noise on the local loop may prevent the use of closely spaced points for a desired error rate.
2. Shell Mapping
Shell mapping is a prior art technique of assigning transmit data bits to constellation points, or symbols. Shell mapping requires that an encoder group symbols together in mapping frames, typically consisting of eight symbols. The constellation is divided into a set of rings that are generally concentric, with an equal number of points per ring. A block of transmit data bits is then used to select a sequence of ring indices and to select the points to send from each of the selected rings.
For purposes of determining the most desirable sequence of rings to select, each ring is assigned a cost value associated with its distance from the origin. The costs are generally representative of the power needed to transmit a point from within that ring. For each possible sequence of rings, a total cost is calculated. The ring index selector/encoder is designed to prefer the least-cost ring sequences, i.e., low-powered point sequences are preferred over high-power point sequences. Note that the above scheme of eliminating certain ring sequences is only possible when there is signal set redundancy. This requires the constellations to be larger than would otherwise be required in systems that do not utilize shell mapping. Furthermore, because the excluded ring sequences are those that include large numbers of outer rings and the favored ring sequences are those that include large numbers of inner rings, the transmitted constellation points will have a non-equi-probable distribution. As a result, the shell mapping technique tends to reduce average power for a given spacing between points (called d.sub.min), thereby increasing the peak-to-average power ratio (PAR).
The reduction in average power (compared to an equi-probable point distribution) can be exploited in an average power constrained system by increasing the distance between points until the average power is equal to an equivalent system with equiprobable point distribution. The receiver sees points with improved d.sub.min that are easier to detect in the presence of noise. Generally, the possible improvement is less than 2.0 dB, and the practically realizable benefit is about 0.5 to 1.0 dB.
The advantage of shell mapping applies to a system where the points are equally distributed within the signal space. This means that the spacing between points in the center of the constellation is the same as the spacing between points at the outer edge. This is not the case in PCM modems where the constellation points are inherently unequally spaced. There is a strong incentive to minimize constellation size in such a scenario. As shown in FIG. 3, the codes in a PCM codec are arranged in segments of 16 members each, with each higher amplitude segment having twice the spacing of the next lower segment. Constellation expansion involves adding more low-power points that are spaced closer together than high-power points. In some cases, the addition of a single point can reduce minimum spacing dramatically. Thus the idea of expanding the constellation to achieve better d.sub.min may have the opposite effect, and reduce it.
It is clear that traditional shell mapping has disadvantages when utilized in a system having constraints on signal point selection that are inherent in PCM modems. Described herein is an improved signal mapping method that includes features of Multiple Modulus Conversion to obtain an effective signal mapping technique.